package qjc.g_链表;

import com.链表.练习题.ListNode;

public class g8_删除链表的倒数第N个节点 {
    /**
     * 创建一个虚拟头节点，方便操作，初始化两个指针 p1 和 p2，都指向虚拟头节点，
     * 移动 p2 指针，使其领先 p1 指针 n + 1 个节点，
     * 移动 p1 和 p2 指针，直到 p2 到达链表末尾，
     * 此时 p1 指向的是倒数第 N 个节点的前一个节点，
     * 删除倒数第 N 个节点，返回结果链表（虚拟头节点的下一个节点）
     */
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode s = new ListNode(-1,head);
        ListNode p1 = s;
        ListNode p2 = s;
        for (int i = 0; i < n + 1; i++) {
            p2 = p2.next;
        }
        while (p2 != null){
            p1 = p1.next;
            p2 = p2.next;
        }
        p1.next = p1.next.next;
        return s.next;
    }
}
